1. Field of the Invention
The present invention generally relates to the field of artificial intelligence and, more particularly, to a device that simplifies and speeds up a heuristic search method by implementing in hardware the computation required for adaptive reordering of sequential decisions in expert systems.
2. Background of the Invention
The invention is intended to be used with algorithms that adaptively reorder a sequence of decisions so that the average time to execute the decisions is minimized. The idea of ordering the outcomes of decisions to improve performance is explored, for example, in the following articles: Wayne E. Smith, "Various Optimizers for Single Stage Production", Naval Research Logistics Quarterly, 3 (1956), pp. 59-66; Herbert A. Simon and Joseph B. Kadane, "Optimal Problem-Solving Search: All-or-None Solutions", Artificial Intelligence, (3), 1975, pp. 235-247; and Ronald Rivest, "On Self-Organizing Sequential Search Heuristics", Communications of the ACM, vol. 19, no. 2, Feb. 1976, pp. 63-67.
A problem-solving system that uses forward reasoning and whose operators each work by producing a single new object or state in a database of information is said to represent problems in a state-space representation. The general idea of a state-space search algorithm that uses heuristic information to decide which node to expand next is always to expand the node that seems the most promising. An algorithm that implements this idea is called an ordered search or best-first search algorithm. Optimal ordering is a function of the frequency of success and the cost of evaluating the outcome. Adaptive reordering is useful in searching simple lists and data bases, and in ordering rules to examine in expert-systems programs. See generally Avron Barr and Edward A. Feigenbaum, editors, The Handbook of Artificial Intelligence, vol. 1, "Heuristic State-Space Search", pp. 58 et seq., HeurisTech Press (1981).
Costs and probabilities can be estimated during program execution in order to create adaptive searches that eventually converge to an optimal ordering. Rivest, supra, describes two techniques that converge to the optimal ordering in the special case in which all costs are unit costs. The problem is best illustrated by way of example. Assume that we have a list of decisions, each with a Yes/No outcome. Our objective is to go through the list of decisions, one at a time, evaluating each decision and examining its outcome until we reach a decision that yields a Yes outcome. At this point we terminate. We wish to order the decisions so that the time to reach the first successful outcome is minimum for the average case.
The central idea of the reordering is to compute for each decision the ratio p/c, where p is the probability of a successful outcome of the decision, and c is the cost of computation to make that decision. The optimum ordering of decisions is in descending order of the ratio p/c. This ratio need not be known beforehand because it can be estimated during program execution. The probability p for a given decision rule is estimated as the ratio of the number of successes divided by the total number of calculations of the decision. The cost c is estimated as the ratio of the total expended time for all evaluations of a rule divided by the number of decision calculations for that rule. The ratio p/c is then estimated by the number of successes for a rule divided by the total time expended in evaluating the rule. The number of decision calculations is a factor common to both numerator and denominator of p/c and thus cancels out when computing the ratio.
Based on the size of the data base, the number of divisions required to compute the ratios p/c for each of the rules will determine the time required for reordering the decisions in the adaptive search. Multiplications and divisions are among the most time consuming, and hence expensive, calculations that may be made by a computer. Thus, for a very large data base the optimal reordering of the search may itself become very expensive.